//二叉搜索树的后序遍历序列: https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?
class Solution {
  public:
    bool VerifySquenceOfBSTCore(vector<int>& sequence, int start, int end) {
        if (start >= end)
        {
            //在不断查找过程中，区域不断缩小，为空时，证明之前的所有范围都满足检测条件
            //也就是是一个BST
            return true;
        }
        //拿到root节点的值
        int root = sequence[end];
        //先遍历左半部分，也就是整体都要比root小，拿到左子树序列
        int i = start;
        while (i < end && sequence[i] < root) 
        {
            i++;
        }
        //在检测右子树是否符合大于root的条件，要从i开始，也就是右半部分的开始
        for (int j = i; j < end; j++) 
        {
            if (sequence[j] < root) 
            {
                //在合法位置处，当前值小于root，不满足BST定义
                return false;
            }
        }
        //走到这里，就说明，当前序列满足需求。但并不代表题目被解决了，还要在检测left和right各自是否也满足
        return VerifySquenceOfBSTCore(sequence, 0, i - 1) && VerifySquenceOfBSTCore(sequence, i, end - 1);
    }
    bool VerifySquenceOfBST(vector<int> sequence) 
    {
        if (sequence.empty()) {
            return false;
        }
        return VerifySquenceOfBSTCore(sequence, 0, sequence.size() - 1);
    }
};